package w5_c1_mergesort;

import selectionSort.ArrayGenerator;
import selectionSort.SortingHelper;

import java.util.Arrays;

/**
 * 自己的归并排序类。
 */
public class MyMergeSort {


    /**
     * 为了统一接口添加的方法 。写的有写臃肿，但毕竟是自己实现的。 还是加个火腿吃XD
     * @param <E>
     * @param arr
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        mergeSort(arr);
    }

    /**
     * 测试MergeSort
     * n为数组长度。
     *
     * @param args
     */
    public static void main(String[] args) {
        int n = 100000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);

        SortingHelper.sortTest("SelectionSort", arr2);
        SortingHelper.sortTest("InsertionSort", arr3);
        SortingHelper.sortTest("MergeSort", arr);
//        printArray(arr);
//        mergeSort(arr);
//        printArray(arr);
    }

    /**
     * 将整个的arr中 数据打印输出。
     *
     * @param arr
     */
    private static<E extends Comparable<E>> void printArray(E[] arr) {
        System.out.print("====Start ");
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%d, ", arr[i]);
        }
        System.out.println("End====");
    }

    /**
     * 将arr[start, end] 数据组成String数组并返回。
     *
     * @param arr
     * @param start
     * @param end
     * @return
     */
    private static String printArray(int[] arr, int start, int end) {
        StringBuilder res = new StringBuilder();
        res.append("[ ");
        for (int i = start; i < end; i++) {
            res.append(arr[i] + ", ");
        }
        res.append("]");
        res.append(start + " to " + end);
//        res.append(" End.");
        return res.toString();
    }

    /**
     * 归并排序。
     *
     * @param arr
     */
    private static <E extends Comparable<E>> void mergeSort(E[] arr) {
        mergeSortHelper(arr, 0, arr.length - 1, 1);

    }

    /**
     * 虽然叫 print***，但并没有打印，而是返回一个String，
     * 其描述了MergeSort函数的运行数据（如运行深度，正在merge的区间）。
     *
     * @param arr
     * @param l
     * @param h
     * @param depth
     * @return
     */
    private static String printMergeSortMessage(int[] arr, int l, int h, int depth) {
        StringBuilder res = new StringBuilder();
        res.append("Depth: " + depth + " ");
        for (int i = 0; i < depth; i++) {
            res.append(">");
        }
        res.append(printArray(arr, l, h));
        res.append("\n");
        return res.toString();

    }

    /**
     * 递归实现归并排序。出口条件是数组为空（即l>h)或 数组只有一个数据（即l==h）。
     *
     * @param arr
     * @param l
     * @param h
     * @param depth
     */
    private static<E extends Comparable<E>> void mergeSortHelper(E[] arr, int l, int h, int depth) {
//        System.out.printf("\nIn call, %s", printMergeSortMessage(arr, l, h, depth));
        if (l >= h) {
//            System.out.printf("Out call, %s", printMergeSortMessage(arr, l, h, depth));
            return;
        }
//        int mid = (l + h) / 2;
        //上面那种方式可能越界，而下面这种方式永远不会越界。
        int mid = l + (h-l) /2;
        mergeSortHelper(arr, l, mid, depth + 1);
        mergeSortHelper(arr, mid + 1, h, depth + 1);
        merge(arr, l, mid, mid + 1, h);
//        System.out.printf("Out call, %s", printMergeSortMessage(arr, l, h, depth));
    }

    /**
     * 归并函数。将arr[l1,h1] 和arr[l2,h2]中数据从小到大排序好，并重新存入arr[l1,h2]。
     * 其实不需要l2这个参数的。但是一开始这么写了，就这么着吧。l2==l1恒成立
     *
     * @param arr
     * @param l1
     * @param h1
     * @param l2
     * @param h2
     */
    private static<E extends Comparable<E>> void merge(E[] arr, int l1, int h1, int l2, int h2) {
//        System.out.printf("Now merge arr [%d, %d] and [%d, %d]\n", l1, h1, l2, h2);
//        E[] res =(E[]) new Object[h2 + h1 - l1 - l2 + 2];
        // TODO:1
        E[] res = Arrays.copyOfRange(arr,l1,h2+1);//上面的创建过程失败了。不知道怎么改，就copy了一下。
        int i = 0;
        E min;
        while (l1 <= h1 && l2 <= h2) {
            if (arr[l1].compareTo( arr[l2]) < 0) {
                min = arr[l1];
                l1++;
            } else {
                min = arr[l2];
                l2++;
            }
            res[i] = min;
            i++;
        }
        while (l1 <= h1) {
            res[i] = arr[l1];
            l1++;
            i++;
        }
        while (l2 <= h2) {
            res[i] = arr[l2];
            l2++;
            i++;
        }
        i--;
        while (i >= 0) {
            arr[h2] = res[i];
            i--;
            h2--;
        }
//        System.out.println("Merge ok.");
    }

    /**
     * 自底向上实现归并排序。
     * @param data
     * @param <E>
     */
    public static <E extends Comparable<E>> void sortBU(E[] data) {

    }

}
